package lc.链表;

import java.util.HashMap;
import java.util.Map;

/**
 * @description: 最近最少使用缓存
 * @author: qian
 * @createDate: 2021/9/10
 */
public class LRUCache {

    class Node{

        private Node prev;
        private Node next;
        int k,v;
        private Node(int k, int v) {
            this.k = k;
            this.v = v;
        }
    }

    public Node head;
    public Node tail;
    public Map<Integer,Node> map;
    int size,capacity;
    public LRUCache(int capacity) {
        head = new Node(0,0);
        tail= new Node(0,0);
        // 连接
        head.next = tail;
        tail.prev = head;
        map = new HashMap<>();
        size = 0;
        this.capacity = capacity;

    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }else {
            Node node = map.get(key);
            remove(key);
            addHead(key, node.v);
            return node.v;
        }

    }

    public void put(int key, int value) {
        if(!map.containsKey(key)) {
            addHead(key, value);
        }else {
            remove(key);
            addHead(key, value);
        }

    }

    private void remove(int key) {

        Node node = map.get(key);
        Node prev = node.prev;
        Node next = node.next;
        prev.next = next;
        next.prev = prev;
        size--;
        map.remove(key);
    }

    private void addHead(int key, int v) {
        // 加到最前
        Node node = new Node(key,v);
        Node next = head.next;
        head.next = node;
        node.next = next;
        next.prev = node;
        node.prev = head;
        map.put(key,node);
        size++;
        if (size > capacity) { // 超出容量
            Node firstNode = tail.prev;
            remove(firstNode.k);
        }

    }
}

